package edu.whu.rose.clock.kps.graph;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.HashMap;

import edu.whu.rose.clock.ssql.graph.RRadiusSubGraph;
import edu.whu.rose.clock.ssql.util.ExpandableIntArray;
import edu.whu.rose.clock.ssql.util.SequentialIntArray;

/**
 * @author clock
 * 
 */
public class GraphMatrix {

	protected final int n; // number of vertexes
	protected int m; // number of edges
	// protected HashMap<Integer, GraphVertex> vertexes;

	protected HashMap<Integer, GraphEdge> rowHeads;
	protected HashMap<Integer, GraphEdge> columnHeads;

	public GraphMatrix(int n) {
		this.n = n;
		this.rowHeads = new HashMap<Integer, GraphEdge>();
		this.columnHeads = new HashMap<Integer, GraphEdge>();
	}

	// protected void loadVertexes() {
	// vertexes = new HashMap<Integer, GraphVertex>();
	// for (int i = 0; i < n; i++) {
	// vertexes.put(new Integer(i + 1), new GraphVertex(i + 1));
	// }
	// }

	public void loadEdges(String dataFile) {
		this.fillDiagonal();
		try {
			BufferedReader br = new BufferedReader(new FileReader(dataFile));
			while (br.ready()) {
				String line = br.readLine().trim();
				String edge = line.substring(line.lastIndexOf(" ") + 1);
				int pos1 = edge.indexOf("-->");
				int pos2 = edge.indexOf(":");
				if (pos1 == -1 || pos2 == -1) {
					System.err.println("Found a wrong edge: " + edge);
					continue;
				}
				int row = new Integer(edge.substring(0, pos1)).intValue();
				int column = new Integer(edge.substring(pos1 + 3, pos2))
						.intValue();
				if (row != column) {
					this.insert(row, column);
					this.insert(column, row);
					m++;
				}
			}
			System.out.println("Loading finished");
			br.close();
		} catch (IOException ex) {
			ex.printStackTrace();
		}
	}

	public RRadiusSubGraph extractSubgraph(int source, int radius) {
		SequentialIntArray vertexes = new SequentialIntArray();
		vertexes.insert(source);
		ExpandableIntArray neighbors = new ExpandableIntArray();
		neighbors.add(source);

		// breadth-first
		for (int i = 0; i < radius; i++) {
			SequentialIntArray newVertexes = new SequentialIntArray();
			ExpandableIntArray newNeighbors = new ExpandableIntArray();
			for (int j = 0; j < neighbors.getSize(); j++) {
				int[] temp = genNeighbors(source);
				for (int k = 0; k < temp.length; k++) {
					if (vertexes.binarySearch(temp[k]) == -1) {
						newVertexes.insert(temp[k]);
						newNeighbors.add(temp[k]);
					}
				}
			}
			neighbors = newNeighbors;
			for (int j = 0; j < newVertexes.getCapacity(); j++) {
				vertexes.insert(newVertexes.get(j));
			}
		}
		return new RRadiusSubGraph(source, vertexes.getArray());
	}

	public RRadiusSubGraph extractSubgraph(int source, int radius,
			double upperBound, double lowerBound) {
		SequentialIntArray vertexes = new SequentialIntArray();
		vertexes.insert(source);
		ExpandableIntArray neighbors = new ExpandableIntArray();
		neighbors.add(source);

		// breadth-first
		for (int i = 0; i < radius; i++) {
			SequentialIntArray newVertexes = new SequentialIntArray();
			ExpandableIntArray newNeighbors = new ExpandableIntArray();
			for (int j = 0; j < neighbors.getSize(); j++) {
				int[] temp = genNeighbors(neighbors.get(j));
				for (int k = 0; k < temp.length; k++) {
					if (vertexes.binarySearch(temp[k]) == -1) {

						// if the current subgraph size is going to surpass the
						// upper bound
						if (vertexes.getCapacity() + newVertexes.getCapacity() == upperBound) {
							return new RRadiusSubGraph(source, vertexes
									.getArray());
						}
						newVertexes.insert(temp[k]);
						newNeighbors.add(temp[k]);
					}
				}
			}
			neighbors = newNeighbors;
			for (int j = 0; j < newVertexes.getCapacity(); j++) {
				vertexes.insert(newVertexes.get(j));
			}
		}

		// if the final subgraph size is smaller than the lower bound
		if (vertexes.getCapacity() < lowerBound) {

		}

		return new RRadiusSubGraph(source, vertexes.getArray());
	}
	
	public RRadiusSubGraph extractSubgraph(int source, int radius,
			double upperBound, double lowerBound, double neighborBound) {
		if (source < 1) {
			return null;
		}
		
		
		SequentialIntArray vertexes = new SequentialIntArray();
		vertexes.insert(source);
		ExpandableIntArray neighbors = new ExpandableIntArray();
		neighbors.add(source);

		// breadth-first
		for (int i = 0; i < radius; i++) {
			SequentialIntArray newVertexes = new SequentialIntArray();
			ExpandableIntArray newNeighbors = new ExpandableIntArray();
			for (int j = 0; j < neighbors.getSize(); j++) {
				int[] temp = genNeighbors(neighbors.get(j));
				for (int k = 0; k < temp.length; k++) {
					if (vertexes.binarySearch(temp[k]) == -1) {

						// if the current subgraph size is going to surpass the
						// upper bound
						if (vertexes.getCapacity() + newVertexes.getCapacity() == upperBound) {
							return new RRadiusSubGraph(source, vertexes
									.getArray());
						}
						newVertexes.insert(temp[k]);
						newNeighbors.add(temp[k]);
					}
				}
			}
			neighbors = newNeighbors;
			for (int j = 0; j < newVertexes.getCapacity(); j++) {
				vertexes.insert(newVertexes.get(j));
			}
		}

		// if the final subgraph size is smaller than the lower bound
		if (vertexes.getCapacity() < lowerBound) {

		}

		return new RRadiusSubGraph(source, vertexes.getArray());
	}

	public int[] genNeighbors(int source) {
		GraphEdge re = rowHeads.get(new Integer(source));
		ExpandableIntArray neighbors = new ExpandableIntArray();

		while (re != null) {
			int gv = re.getDestination();
			neighbors.add(gv);
			re = re.getNextEdgeFromSource();
		}

		return neighbors.toArray();
	}
	
	public int[] getEnds(int source) {
		GraphEdge ge = rowHeads.get(new Integer(source));
		ExpandableIntArray neighbors = new ExpandableIntArray();

		while (ge != null) {
			int gv = ge.getDestination();
			// only return the edges in which end is larger than source
			if (gv > source) {
				neighbors.add(gv);
			}
			ge = ge.getNextEdgeFromSource();
		}

		return neighbors.toArray();
	}

	public void insert(int source, int destination) {
//		if (source > n | destination > n | source < 1 | destination < 1) {
//			System.err.println("Error: illegal edge (" + source + ","
//					+ destination + ")");
//			return;
//		}
		Integer s = new Integer(source);
		Integer d = new Integer(destination);
		GraphEdge newEdge = new GraphEdge(source, destination);
		GraphEdge rowHead = this.rowHeads.get(s);
		GraphEdge columnHead = this.columnHeads.get(d);
		if (rowHead == null) {
			this.rowHeads.put(s, newEdge);
		} else {
			if (rowHead.getDestination() > destination) {
				newEdge.setNextEdgeFromSource(rowHead);
				this.rowHeads.put(s, newEdge);
			} else if (rowHead.getDestination() < destination) {
				GraphEdge re = null;
				for (re = rowHead; re.getNextEdgeFromSource() != null
						&& re.getNextEdgeFromSource().getDestination() < destination; re = re
						.getNextEdgeFromSource())
					;
				if (re.getNextEdgeFromSource() == null) {
					re.setNextEdgeFromSource(newEdge);
				} else {
					if (re.getNextEdgeFromSource().getDestination() > destination) {
						newEdge.setNextEdgeFromSource(re
								.getNextEdgeFromSource());
						re.setNextEdgeFromSource(newEdge);
					}
					else {
						if (source > destination)
						m--;
					}
				}
			}
		}
		if (columnHead == null) {
			this.columnHeads.put(d, newEdge);
		} else {
			if (columnHead.getSource() > source) {
				newEdge.setNextEdgeToDestination(columnHead);
				this.columnHeads.put(d, newEdge);
			} else if (columnHead.getSource() < source) {
				GraphEdge re = null;
				for (re = columnHead; re.getNextEdgeToDestination() != null
						&& re.getNextEdgeToDestination().getSource() < source; re = re
						.getNextEdgeToDestination())
					;
				if (re.getNextEdgeToDestination() == null) {
					re.setNextEdgeToDestination(newEdge);
				} else {
					if (re.getNextEdgeToDestination().getSource() > source) {
						newEdge.setNextEdgeToDestination(re
								.getNextEdgeToDestination());
						re.setNextEdgeToDestination(newEdge);
					}
				}
			}
		}
	}

	public void fillDiagonal() {
		for (int i = 1; i < n + 1; i++) {
			this.insert(i, i);
		}
	}

	public HashMap<Integer, GraphEdge> getRowHeads() {
		return rowHeads;
	}

	public HashMap<Integer, GraphEdge> getColumnHeads() {
		return columnHeads;
	}

	public int getN() {
		return n;
	}

	public int getM() {
		return m;
	}

}
